// https://leetcode.cn/problems/4sum/
package leet18sum4

import "sort"

// 思路：
// 和三数之和的思路类似，先来一个四重循环解决的办法。
// 1. 定义一个二维切片，用于存储符合条件的四个数
// 2. 对数组进行排序
// 3. 遍历数组，寻找符合条件的四个数
// 4. 第一重循环就可以先决的过滤掉很多不符合条件的数字
// 5. 【过滤1】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
// 6. 【过滤2】如果当前数字和上一个数字相同，跳过
// 7. 第二重循环（先不使用左右指针，原始的循环）
// 8. 【过滤3】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
// 9. 【过滤4】如果当前数字和上一个数字相同，跳过
// 10. 第三重循环（先不使用左右指针，原始的循环）
// 11. 【过滤5】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
// 12. 【过滤6】如果当前数字和上一个数字相同，跳过
// 最后一重循环也是这个样!!!
func FourSum(nums []int, target int) [][]int {
	// 定义一个二维切片，用于存储符合条件的四个数
	res := [][]int{}
	// 对数组进行排序
	sort.Ints(nums)
	// 遍历数组，寻找符合条件的四个数
	for i := 0; i < len(nums)-3; i++ {
		// 【过滤1】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
		if nums[i] > target {
			return res
		}
		// 【过滤2】如果当前数字和上一个数字相同，跳过
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			// 【过滤3】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
			if nums[i]+nums[j] > target {
				break
			}
			// 【过滤4】如果当前数字和上一个数字相同，跳过
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			for k := j + 1; k < len(nums)-1; k++ {
				// 【过滤5】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
				if nums[i]+nums[j]+nums[k] > target {
					break
				}
				// 【过滤6】如果当前数字和上一个数字相同，跳过
				if k > j+1 && nums[k] == nums[k-1] {
					continue
				}
				for l := k + 1; l < len(nums); l++ {
					if nums[i]+nums[j]+nums[k]+nums[l] == target {
						res = append(res, []int{nums[i], nums[j], nums[k], nums[l]})
					}
					if l > k+1 && nums[l] == nums[l-1] {
						continue
					}
				}
			}
		}
	}
	return res
}

// 思路二：
// 使用双指针法，先对数组进行排序，然后使用两个指针分别指向数组的头和尾，
// 通过移动指针来寻找符合条件的四个数。
// 这种方法的时间复杂度为O(n^3)，空间复杂度为O(1)。
// 这种方法的时间复杂度比四重循环的方法要快很多，
// 但是空间复杂度还是O(n)，因为需要存储结果。
func fourSumWithDoublePointer(nums []int, target int) [][]int {
	// 定义一个二维切片，用于存储符合条件的四个数
	res := [][]int{}
	// 对数组进行排序
	sort.Ints(nums)
	// 遍历数组，寻找符合条件的四个数
	for i := 0; i < len(nums)-3; i++ {
		// 【过滤1】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
		if nums[i] > target {
			return res
		}
		// 【过滤2】如果当前数字和上一个数字相同，跳过
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			// 【过滤3】如果当前数字大于target，说明后面的数字都大于target，直接返回结果
			if nums[i]+nums[j] > target {
				break
			}
			// 【过滤4】如果当前数字和上一个数字相同，跳过
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			left := j + 1
			right := len(nums) - 1
			for left < right {
				sum := nums[i] + nums[j] + nums[left] + nums[right]
				if sum == target {
					res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
					left++
					right--
					for left < right && nums[left] == nums[left-1] {
						left++
					}
					for left < right && nums[right] == nums[right+1] {
						right--
					}
				} else if sum < target {
					left++
				} else {
					right--
				}
			}
		}
	}
	return res
}
